A matrix is a rectangular array of numeric or algebraic quantities subject to mathematical operations, e.g., multiplication, addition, subtraction, etc. Matrices are typically used to solve systems of equations where there are multiple variables to be computed. A matrix is especially useful in processing large quantities of numbers and unknowns, which can otherwise be difficult by individual computation. For example, matrices may be used to determine the vibrational resonance of a car engine, evaluate the electronic structure of a molecule, model heat transfer within a closed system, aid in rotation and translation of computer graphics, etc. The applications listed above are typically carried out on supercomputers.[A][B]=[C]  (1a)                         
                                          [                                                                                a                    11                                                                                        a                    12                                                                                                                    a                    21                                                                                        a                    22                                                                        ]                    ⁡                      [                                                                                b                    11                                                                                        b                    12                                                                                                                    b                    21                                                                                        b                    22                                                                        ]                          =                  [                                                                      c                  11                                                                              c                  12                                                                                                      c                  21                                                                              c                  22                                                              ]                                    (1b)            
Equations (1a) and (1b) shown above illustrate a typical matrix-matrix multiplication. A first matrix [A] has two rows and two columns and is referred to in the art as a 2×2 matrix. The first matrix [A] has four elements: a11, a12, a21, and a22. A second 2×2 matrix [B] also has four elements: b11, b12, b21, and b22. A third 2×2 matrix [C] contains the result of the multiplication of the first matrix [A] and the second matrix [B]. The resulting third 2×2 matrix [C] has four elements: c11, c12, c21, and c22. To calculate the value of all the elements in the third 2×2 matrix [C] using the traditional method for matrix-matrix multiplication, equations (2) through (13) shown below are used.s1=a11b11  (2)s2=a12b21  (3)s3=a11b12  (4)s4=a12b22  (5)s5=a21b11  (6)s6=a22b21  (7)s7=a21b12  (8)s8=a22b22  (9)c11=s1+s2  (10)c12=s3+s4  (11)c21=s5+s6  (12)c22=s7+s8  (13)
As demonstrated above, multiplying two 2×2 matrices, using the traditional method, requires 8 multiplication operations and 4 addition operations. As the size of the matrices being multiplied becomes larger, the number of multiplication operations and addition operations increases on the order of the cube of the matrix size, denoted O(n3). Due to the larger computational cost of these operations, a number of methods have been developed to decrease the number of computation steps.
One such method is the Strassen method. The Strassen method recursively divides a matrix into smaller sub-matrices upon which the arithmetic savings of requiring only 7 multiplication operations are applied at each level of recursion. The Strassen method is typically employed for matrices that are greater than 128×128 or larger, depending on the computational resources being used. While the Strassen method typically provides a significant decrease in computation time, the method introduces a precision loss due to an uneven distribution of arithmetic in the result matrix. Thus, while the computation of a matrix multiplication requires fewer computation steps using the Strassen method, the end result may be less precise than would occur using traditional methods. In this context, precision is defined as the number of significant digits to which a value may be reliably measured.
To further reduce computation steps by the Strassen method, many variant methods have been created. The Winograd variant of the Strassen method provides a balanced trade-off between decreased additions and increased memory requirements and complexity.
Equations (14)–(34) illustrate application of the Winograd variant of the Strassen method for matrix-matrix multiplication for the previously defined 2×2 matrices [A] and [B] in equation (1b).s1=a21+a22  (14)s2=s1−a11  (15)s3=a11−a21  (16)s4=a12−s2  (17)s5=b12−b11  (18)s6=b22−s5  (19)s7=b22−b12  (20)s8=s6−b21  (21)m1=s2s6  (22)m2=a11b11  (23)m3=a12b21  (24)m4=s3s7  (25)m5=s1s5  (26)m6=S4b22  (27)m7=a22s8  (28)t1=m1+m2  (29)t2=t1+m4  (30)c11=m2+m3  (31)c12=t1+m5+m6  (32)c21=t2−m7  (33)c22=t2+m5  (34)
As demonstrated above, multiplying two 2×2 matrices using the Strassen/Winograd method requires 7 multiplication operations and 15 addition operations. The power of Strassen methods comes from the recursion. The 2×2 matrix elements may themselves be matrices so that a reduction in arithmetic is achieved at each level of recursion. The number of multiplication operations and addition operations increases on an order approaching Log2(7) of the matrix size, denoted O(n2.8). Due to the high computational costs of matrix multiplication operations, a number of methods have been developed to decrease the number of computation steps.
As the dimensions of the matrices being multiplied increases, i.e., an increase in the number of rows and/or columns, the required computation increases exponentially creating a necessity for a recursive computational method to subdivide and more accurately solve for the unknowns. A threshold occurs where the Winograd variation of the Strassen method is more efficient than the traditional matrix-matrix multiplication method is described as a crossover point. Essentially, the Winograd variation of the Strassen method is used recursively to perform the matrix-matrix multiplication until the crossover point is reached. Once the crossover point is reached, the traditional matrix-matrix multiplication method is more efficient than the Winograd variation of the Strassen method.
The precision loss introduced by the Winograd variation of the Strassen method is typically seen in matrix-matrix multiplication using floating point numbers. A floating-point number is a number represented by a mantissa and an exponent according to a given base. The mantissa is usually a value between zero and one. To find the value of a floating-point number, the base is raised to the power of the exponent, and the mantissa is multiplied by the result. Ordinary scientific notation uses floating-point numbers with 10 as the base. In a computer, the base for the floating-point number is usually two. Precession loss typically arises in floating point number calculations through round-off errors. Round-off errors are a result of rounding results of floating-point operations (e.g., multiplication steps in matrix-matrix multiplication) during mathematical calculations.